# Description

Luogu 传送门

# Solution

观察到数据范围：状压就你了！

于是我们快乐地使用状压 $dp$ 来解决这个问题。

首先我们开一个 $match[i][j]$ 数组表示所有字符串第 $i$ 位能否匹配 $j \in a···z$ （这个描述起来有点抽象，可以根据代码理解一下）。

然后就是 $dp$ 了，我们设 $dp[i][k]$ 表示第 $i$ 位匹配 $k(k \in a···z)$ 的方案数。

转移方程：

$dp[i + 1][match[i][k] \& j] += dp[i][j]$

最后再按位枚举，统计答案即可。

	#include <bits/stdc++.h>

	using namespace std;

	const int N = 55;
	const int p = 1e6 + 3;
	int T, n, m;
	int dp[N][1 << 15], match[N][N];
	char s[N][N];

	int main(){
	scanf("%d", &T);
	while(T--){
	memset(dp, 0, sizeof(dp));
	memset(match, 0, sizeof(match));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) scanf("%s", s[i]);
	int len = strlen(s[1]);
	for(int i = 0; i < len; ++i)
	for(int j = 0; j < 26; ++j)
	for(int k = 1; k <= n; ++k)
	if(s[k][i] == '?' \|\| s[k][i] - 'a' == j)
	match[i][j] \|= (1 << (k - 1));
	int sta = (1 << n) - 1;
	dp[0][sta] = 1;
	for(int i = 0; i < len; ++i)
	for(int j = 0; j <= sta; ++j)
	if(dp[i][j])
	for(int k = 0; k < 26; ++k)
	dp[i + 1][match[i][k] & j] = (dp[i + 1][match[i][k] & j] + dp[i][j]) % p;
	int ans = 0;
	for(int i = 0, res = 0; i <= sta; ++i, res = 0){
	for(int j = 1; j <= sta; j <<= 1) res += (bool)(i & j);
	if(res == m) ans = (ans + dp[len][i]) % p;
	}
	printf("%d\n", ans);
	}
	return 0;
	}